#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return;
        
        // 步骤1：从右往左找第一个小于右边某个数字的位置
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        
        // 如果i < 0，说明整个数组是降序的，已经是最大排列
        // 需要返回最小排列（即整个数组反转）
        if (i < 0) {
            reverse(nums.begin(), nums.end());
            return;
        }
        
        // 步骤2：从右往左找第一个大于nums[i]的数字
        int j = n - 1;
        while (j > i && nums[j] <= nums[i]) {
            j--;
        }
        
        // 步骤3：交换nums[i]和nums[j]
        swap(nums[i], nums[j]);
        
        // 步骤4：将i+1到末尾的所有数字反转（使其变为升序）
        reverse(nums.begin() + i + 1, nums.end());
    }
};

void test01() {
    vector<int> input = {1, 2, 3};
    Solution obj;
    obj.nextPermutation(input);

    for (auto item : input) {
        cout << item << " ";
    }
    cout << endl;
}

void test02() {
    vector<int> input = {3, 2, 1};
    Solution obj;
    obj.nextPermutation(input);

    for (auto item : input) {
        cout << item << " ";
    }
    cout << endl;
}

void test03() {
    vector<int> input = {1, 1, 5};
    Solution obj;
    obj.nextPermutation(input);

    for (auto item : input) {
        cout << item << " ";
    }
    cout << endl;
}


int main() {
    std::cout << "this is Leetcode-31-demo." << std::endl;
    cout << "test01:" << endl;
    test01();

    cout << "test02:" << endl;
    test02();

    cout << "test03:" << endl;
    test03();

    return 0;
}
